package com.Earth01;
/*
* LeedCode 441.排列硬币
* */
public class Earth240704 {
    public static void main(String[] args) {
        int n = 1804289383;
        int i = arrangeCoins(n);
        System.out.println(i);
    }
    /*
    * left,right,mid 分别为左面，右面，中间元素
    * x为硬币数，也为最大的台阶数
    * sumI 为前I台阶所需硬币数量
    * */
    public static int arrangeCoins(int n) {
        if(n == 1) return 1;
        //最多有x层楼梯
        //每层数量分别为i
        //第i层需要 i(i+1)/2 枚硬币
        int left = 1,right = n,mid = 0;
        int sumI;
        int res = 0;
        while(left < right){
            mid = (left + right) >> 1;
            sumI = mid * (mid + 1) / 2;
            if(sumI == n){
                res = mid;
                break;
            }
            if(n < sumI){
                right = mid;
            }else {
                left = mid + 1;
                res = mid;
            }
        }
        return  res;
    }
}
